DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2011.484

Analysis of multi-stage open shop processing systems

Authors: Christian E.J. Eggermont, Alexander Schrijver, and Gerhard J. Woeginger

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract

We study algorithmic problems in multi-stage open shop processing systems that are centered around reachability and deadlock detection questions. We characterize safe and unsafe system states. We show that it is easy to recognize system states that can be reached from the initial state (where the system is empty), but that in general it is hard to decide whether one given system state is reachable from another given system state. We show that the problem of identifying reachable deadlock states is hard in general open shop systems, but is easy in the special case where no job needs processing on more than two machines (by linear programming and matching theory), and in the special case where all machines have capacity one (by graph-theoretic arguments).

Cite as

Christian E.J. Eggermont, Alexander Schrijver, and Gerhard J. Woeginger. Analysis of multi-stage open shop processing systems. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 484-494, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{eggermont_et_al:LIPIcs.STACS.2011.484,
  author =	{Eggermont, Christian E.J. and Schrijver, Alexander and Woeginger, Gerhard J.},
  title =	{{Analysis of multi-stage open shop processing systems}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{484--494},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.484},
  URN =		{urn:nbn:de:0030-drops-30373},
  doi =		{10.4230/LIPIcs.STACS.2011.484},
  annote =	{Keywords: scheduling, resource allocation, deadlock, computational complexity}
}

Document

DOI: 10.4230/LIPIcs.STACS.2008.1347

Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs

Authors: Éric Colin de Verdiére and Alexander Schrijver

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract

Let $G$ be a directed planar graph of complexity~$n$, each arc having a nonnegative length. Let $s$ and~$t$ be two distinct faces of~$G$; let $s_1,ldots,s_k$ be vertices incident with~$s$; let $t_1,ldots,t_k$ be vertices incident with~$t$. We give an algorithm to compute $k$ pairwise vertex-disjoint paths connecting the pairs $(s_i,t_i)$ in~$G$, with minimal total length, in $O(knlog n)$ time.

Cite as

Éric Colin de Verdiére and Alexander Schrijver. Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 181-192, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{colindeverdiere_et_al:LIPIcs.STACS.2008.1347,
  author =	{Colin de Verdi\'{e}re, \'{E}ric and Schrijver, Alexander},
  title =	{{Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{181--192},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1347},
  URN =		{urn:nbn:de:0030-drops-13474},
  doi =		{10.4230/LIPIcs.STACS.2008.1347},
  annote =	{Keywords: Algorithm, planar graph, disjoint paths, shortest path}
}

Search Results

Documents authored by Schrijver, Alexander

Analysis of multi-stage open shop processing systems

Abstract

Cite as

Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message